//
// Created by Administrator on 2021/4/9.
//

/*
翻转一棵二叉树。

示例：

输入：

4
/   \
  2     7
/ \   / \
1   3 6   9
输出：

4
/   \
  7     2
/ \   / \
9   6 3   1
备注:

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <iostream>
#include <vector>

using namespace std;

//definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

void preorder(TreeNode *t, vector<int> &v) { // 前序遍历递归函数
    if (t == nullptr) {
        return;
    }
    v.push_back(t->val);
    preorder(t->left, v);
    preorder(t->right, v);
}

vector<int> preorderTraversal(TreeNode *root) { // 前序遍历入口
    vector<int> ans;
    preorder(root, ans);
    return ans;
}

class Solution {
public:
    TreeNode *invertTree(TreeNode *root) {
        if (root == nullptr) return root;
        invertTree(root->left);
        invertTree(root->right);
        TreeNode *temp;
        temp = root->left;
        root->left = root->right;
        root->right = temp;
        return root;
    }
};
class Solution2 { // 题解 递归
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};


int main() {
    auto t7 = TreeNode(9);
    auto t6 = TreeNode(6);
    auto t5 = TreeNode(3);
    auto t4 = TreeNode(1);
    auto t3 = TreeNode(7, &t6, &t7);
    auto t2 = TreeNode(2, &t4, &t5);
    auto t1 = TreeNode(4, &t2, &t3);
    vector<int> v;
    v = preorderTraversal(&t1);
    cout << "before inversion:" << endl;
    for (auto x:v) cout << x << endl;
    Solution sol;
    sol.invertTree(&t1);
    v = preorderTraversal(&t1);
    cout << "after inversion:" << endl;
    for (auto x:v) cout << x << endl;
    return 0;
}